/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *partition(ListNode *head, int x) {
        ListNode g1(-1), g2(-1), *t1, *t2;
        t1=&g1;
        t2=&g2;
        while (head!=NULL) {
            ListNode *cur=head;
            head=head->next;
            if (cur->val<x) {
                t1->next=cur;
                t1=cur;
            } else {
                t2->next=cur;
                t2=cur;
            }
            cur->next=NULL;
        }
        t1->next=g2.next;
        return g1.next;
    }
};
